Broadcast and multicast enables efficient distribution of contents to large groups of receivers, as schematically illustrated in FIG. 1, for both wireless applications and standard data communications. In the following the term broadcast will be used to refer to both broadcast and multicast. Recent efforts focus broadcast over wireless networks and a key topic is to use the wireless link as efficiently as possible for example to reduce time for media access. Another topic of key interest is to provide secure broadcast. Thus, encryption of contents is an important enabler for commercial broadcast services. From a user point of view, authentication is an important topic. It is desirable that a user can verify that contents and encryption keys originate from an intended party.
Broadcast protection systems normally operate with a number of distinguished steps. A service registration step is usually required in which a user enters an agreement with a service provider. In this step the user is provided with a personal, unique and secret key. In a key-distribution step a media key is distributed to registered users for decryption of broadcast contents. The service provider encrypts the contents in a media delivery protection step. A re-key step is required to update the contents key, e.g. when a new user is registered, a user de-registers or when a media key is compromised. Periodic re-key may also be used to increase the security of the system. Service registration is usually point-to-point between a user and a content provider and may use any secure and authenticated means for communication. Key-distribution and media delivery protection (MDP) will be executed in a one-to-many fashion.
The main problem with key-distribution is to update the MDP-key when new members either join or leave the group in a way, which is scalable to large groups. The naive approach of sending the updated MDP-key encrypted individually for each member does not scale well. There are schemes proposed, referred to as group-key distribution protocols to improve scalability e.g. LKH (Logical Key Hierarchy), SD (Subset Difference) and LSD (Layered Subset Difference). These are examples of hierarchical group key distribution protocols.
To each hierarchical group key distribution protocol there is an associated set of encryption keys. An abstract hierarchical tree can be used in order to illustrate the arrangement of these keys and the relationship between the keys. FIG. 2 illustrates a hierarchical tree with a set of members, M1 to M8, at the bottom. At the top of the hierarchy there is the output key Km of the specific hierarchical protocol. A subgroup of the complete group of members determines a sub-tree of the hierarchical tree that in turn determines a group key management message comprising a set of identifiable message elements. The nodes in the tree model in between the bottom and top levels are associated with encryption keys required for decrypting elements of the group key management message. Each user receives, in an initiation phase, information for deriving a subset of these keys, e.g. all keys on the path between the particular member Mi and the Km. The hierarchical group key distribution protocols provide linear initial keying performance and improved logarithmic re-key performance. These methods are the most scalable and efficient ones because of the non-linear performance.
FIG. 2 can conveniently be used to discuss the LKH method. The LKH method is a scalable group-key distribution protocol, which is based on the approach of associating every node (i) in a tree with a key Ki where (i) is an index in one or several dimensions. The root key, Km is the key associated with the top level of the tree and it is used as the MDP-key. Every member in the group of users is provided with individual keys, e.g. in a registration phase, and these keys are associated with the leaves K(rst) at the bottom of the tree. Every member also receives all the keys lying on the path from its leaf up to the root. A typical message is made of triplets {i>j, [Ki]Kj}, where i>j denotes that node i is an ancestor to node j. A member can decrypt the message part if j is on the path up to the root i.e. Ki can be retrieved by use of the key Kj associated with node j. Thus, the set of Ki comprises hierarchical encryptions of the root key Km, i<m. When updating the MDP-key because of a joining or leaving member, the numbers of required messages are few, as well as the message size. A major drawback is that the system is state-full or state-dependent, i.e. the algorithm makes use of the previous group key to encrypt the new generated group key. Therefore, the dependency of state is required for the scheme. In the case the group key for a certain state is lost it is not possible for the participant to re-catch the session by all means.
Another drawback is that a provided method for batch re-keying, i.e. batch update of keys, is not very efficient in particular at times of major and momentary changes of memberships.
The Subset Cover algorithms is a general class of group-key distribution protocols, characterized in that a group member is associated with a subset of members, the subset being associated with a particular key. The Subset Difference (SD) protocol, illustrated in FIG. 3, is an example of these protocols. With reference to FIG. 3 the nodes are numbered with an index j. Exemplary in FIG. 3 the nodes 2, 3, 5, and 12 are indicated. A collection of subsets Si,j covers the complete group and distinctly determines the set of all members. Si,j denotes the set of leaves under node i but not under node j. In FIG. 3 the sets S2,5 and S3,12 are illustrated. When updating the MDP key, the group of members is exactly covered with these subsets, and the updated key is encrypted under each of the subset keys. The SD (Subset Difference) scheme is a stateless group-key distribution protocol The SD scheme creates a binary tree with as many leaves as possible members. Every possible member is associated with a specific leaf, i.e. users who are not members at the particular moment are also associated with a leaf. The key server (KS) creates the set S of entities Si, j. Every Si, j is also uniquely associated with a key Lij, which every member of the set Si, j can compute, but no other group member. The MDP-key can be updated to a particular set Si, j by encrypting it using Lij. It should be noted that this has to be done for every Si, j belonging to S. The Lij's are created in a hierarchical fashion, where a random seed associated with the node i is extended to nodes j>i using a one-way function iteratively.
The LSD (Layered Subset Difference) scheme is a SD scheme, but with special layers such that every possible member needs to store fewer keys than in the original scheme. In all these systems, the group key management message that is broadcasted to all users is quite large and needs to be authenticated. In unicast, a shared secret key message authentication code (MAC) is used to provide authentication. In broadcast, the group key (MDP) provides a shared secret key, however, performing message authentication with this key only verifies that the sender is a member of the group, but not necessarily the intended source. The naive approach would of course be to authenticate the message as is using a message authentication code or signature. The naive approach of authenticating the entire broadcast message cannot simply tolerate bit errors or packet loss of parts of the group key management message without the authentication failing.
The naive approach is also resource consuming, increasing both computational cost and bandwidth consumption.
Another approach would be to authenticate each encrypted key. This also proves to be resource consuming (both computational and bandwidth consuming). In fact the number of encrypted MDP-keys in SD are at most min (2r−1, n/2, n−r), where n is the total number of members and r is the number of revoked members.
Reference [1] discloses a stateless hierarchical method based on subset cover of the group of users.
The size of a key management message tends to become very large in large groups. Therefore, various attempts have been made to make the broadcast of a key management message as efficient as possible.
Reference [2] discloses a method to arrange the users in dependence of the probability that a user will be compromised thereby allowing for an increased efficiency of the key management system.
Reference [3] discloses authentication of the MDP-key. However, the scalability of this solution is less favorable than that obtained according to the invention. Further, the solution according to reference [3] does not allow for effective optimizations, as the user needs to obtain the entire key management message in order to verify the signature.
Reference [4] discloses a scheme applied to the LKH method in order to introduce authentication. The disclosed scheme is based on the principle that a hash chain generates each key in the tree. When a group member receives a new key, computing a hash over the new key and comparing the hash with the old key can verify its correctness. Although this method creates only a small overhead it is not practical to use in reality as the LKH based re-keying and its authentication can, thereafter, only be applied a limited number of times equal to the length of the hash chain. Furthermore, it will not be possible for the key server to generate the keys by itself if needed.
As mentioned above, a group key management message will become very large when the group of users increases. It would be very resource consuming to frequently multicast or broadcast such messages over a cellular network. There is also a question which party would finance the expensive radio link resources required to transmit the messages. References [5, 6] advice a distributed system of entities each entity managing a subgroup of the full group. Each subgroup is further associated with a separate group key. Although these systems provide scalability they become complex and expensive. Another problem with the cited methods is related to distribution of security functionality to another entity whereby such other entity must be trusted to securely handle the security functionality and also to be able to handle authentication and authorization of users. This makes such systems more exposed to compromise. As a consequence, such systems do not manage optimizations done by entities not trusted with keys or other secret information.
Thus, there is a need for an efficient and reliable method for group-key distribution in broadcast and multicast systems that overcome the drawbacks of prior art systems. In particular there is a need for a method that provides for authentication of the MDP-key at the same time allowing for an optimization of the message. Preferably, the optimization shall be possible without the need to require knowledge of any of the keys used.